This invention relates to telecommunications networks, and more particularly to a time-slotted, pre-allocated, high-speed link in a network where this link exhibits a long propagation delay.
Broadband ISDN (integrated services digital network) systems are prone to severe buffer overflow problems at intermediate nodes. Data is thus lost and must be retransmitted, reducing the reliability and capacity of the system. These losses are referred to as congestion loss, but this is not the result of an under-engineered network. Instead, this type of congestion is an inevitable result of the probabilistic and bursty nature of data in asynchronous (packetized) information transfer.
In narrowband packet networks, feedback control mechanisms are able to manage the traffic load so that buffer overflow can be mostly avoided, or at least controllable. For example, networks based upon the so-called X.25 protocol provide two levels of flow control; one controls all traffic across the physical link, and another layer controls traffic across one virtual circuit. Each layer's protocol provides both a window-based flow manager and a stop/go control mechanism. That is, a node having data to send is only allowed to send a fixed amount of data before being granted permission to continue, and, in addition, the node can be shut off for a time period when capacity is all allocated.
Connectionless networks, such as those using certain DECnet and DDN Internet Protocol, do not have positive controls as in X.25, but still provide definite feedback mechanisms. For example, "implicit" feedback mechanisms focus on sequence numbers in the packets; if a packet is dropped (as may be inferred from a gap in acknowledged sequence numbers) it may be determined that congestion is severe and so the sender drastically reduces its sending rate (as by reducing the window size). Or, "explicit" mechanisms provide warning of incipient congestion, so that senders can usually reduce their rate before any packets are lost; thus there is still feedback, but the data terminals are more responsible for responding to it.
Broadband asynchronous transfer mode (ATM) networks often have links that span large distances, thousands of miles in many cases. Here the propagation delay is too long to allow feedback to be effective. The delay from the time a packet is sent to the time it is received at the destination is much longer than the time during which congestion can cause buffers to fill in intermediate nodes, so data is lost. By the time the loss is recognized and a feedback signal sent back to the sender, it is too late to alter the sending rate or otherwise change the input to prevent congestion.
It is not sufficient to use any of the common feedback schemes, including credit managers, windows, etc., across long-delay ATM networks. While some of these techniques are quite appropriate for short-haul ATM applications, they lose effectiveness when the buffer fill time falls well below the propagation delay in the link. The exact point at which feedback delay becomes unacceptable depends upon the degree of burstiness of the traffic; if the bulk of traffic is constant, then a somewhat longer delay can be tolerated before loss occurs. Highly bursty traffic is more sensitive.
In a typical network, therefore, two types of allocation are needed. A simple credit-based buffer allocation scheme is likely to be quite adequate for certain applications--those links that have short propagation delay. The receiving end of each link monitors the buffers available to each virtual path and/or virtual channel and grants credits to the sending end. This may be somewhat cumbersome when the number of virtual paths is quite high, but in practice credits are allocated back to each virtual path or channel based upon availability of buffers for the links going out of the node. Some amount of receive buffer may be useful in order to permit a node to accept all traffic arriving at one incoming link when there is a disparate buffer fill situation at its outgoing links. Nonetheless, this transmission discipline is simply a form of conventional hop-by-hop management, and is not dis-similar from what is found on conventional connection-oriented packet networks. These links do not need a more complex scheme such as is described below. A more complex discipline is required when the dimensions of the network cause propagation delays to become longer than allowable feedback times.
There are two causes of congestion loss, funnelling and mismatch. A packet-switched network can lose its protocol data units (cells, frames or packets) when the arrival rate at any given point exceeds the departure rate for a long enough period of time that a buffer overflows. This can occur for either of two separate and identifiable reasons. Funneling loss occurs when several different paths converge on a single buffer, and traffic bursts arrive closely spaced in time, such that overflow occurs. Funneling is generally transient. Mismatch occurs when sustained demand for a given facility exceeds its capacity; for example, when a high-speed link meets a lower-speed link, or when an additional virtual circuit is created over a busy facility. A congestion management scheme must be able to handle both mismatch and funneling. However, deferent techniques tend to be more effective for one or the other. Admission control policies, coupled with stringent network-wide resource allocation and a minimum of oversubscription, can minimize mismatch. Connectionless networks require feedback to control mismatch loss, as they rarely if ever provide rate-based control. Traditional packet networks are usually rather tolerant of funneling loss. An occasional dropped packet can be recovered. ATM networks, however, may use protocols that are prone to loss multiplication; a single dropped cell can corrupt an entire packet, if frame-based recovery is used. Some ATM applications, such as circuit emulation, are intolerant of any cell loss. Thus, funneling effects are far more severe in an ATM context, and are hardest to solve.
It has been suggested that by limiting the rate at which users are allowed to send data into an ATM network (i.e., access control) such that the total bandwidth of all channels does not exceed the cross-sectional size of any trunk facility, then congestion will not occur. This is not true, however, when the traffic is bursty. While bursts in an ATM network may be individually bounded in size and rate, a probability exists that at any given time the amount of traffic arriving for any given buffer will exceed the capacity of that buffer, even if the average is not excessive.
The funneling effect is particularly severe when many small virtual channels are provided. If the number of virtual channels exceeds the number of cells in a buffer, then it is statistically possible that many of them send their cells at such times that the bursts arrive at a given buffer close enough in time that the buffer overflows. The total "event horizon" within an ATM network is no greater than the longest round-trip delay including buffer times. Thus, even circuits with a "reserved" throughput class (enforced at the access) of, say, 64-kbps, who are thus allowed to issue one cell (with a 48-octet payload) every 6-ms., can send those cells anywhere within the 6-ms. window, and indeed it is more likely that senders will be allowed to accumulate credits so that larger bursts may be sent with less frequency.
It can therefore be shown that no access control scheme can positively prevent buffer overflow. If ATM networks are to use loss-sensitive protocols, then a different mechanism is required to prevent cell loss. Such a mechanism must actively counter the bursty nature of ATM traffic, to reduce peak buffer occupancy and thus the chance of overflow.
Continuous bit rate services are in this respect little different from variable bit rate services, because typical variable bit rate user variations in rate occur over a time period that is quite long, compared to sub-millisecond buffer fill times. Variable bit rate is thus handled by treating it as a special case of continuous bit rate, in which the bit rate is changed on occasion. Most bursty data applications can tolerate delays in the 100-ms. range; if reallocation of bandwidth takes this long, applications and users will typically not notice.
Circuit-switched digital networks (including narrow bandwidth integrated services digital networks) typically make use of synchronous time division multiplexing to allocate bandwidth on trunk facilities; in this method, individual channels are separated by their position within a stream. Some bandwidth is required for framing purposes, but individual channels have no overhead of their own. Asynchronous transfer mode (ATM) is, in effect, "asynchronous time division multiplexing", where individual channels are identified by label, instead of by position within the stream. Asynchronous transfer mode is thus more akin to packet mode in operation, although it operates below the data link layer and does not provide the same services as narrowband packet networks.
Because the bursty nature of ATM will necessarily result in buffer overflow in heavily-loaded (but not necessarily oversubscribed) networks with long-delay physical facilities, buffer management (i.e., congestion avoidance) requires a redefinition of the problem, as addressed by the present invention.